import random


# 插入排序
# 实现原理 初始时选择第一个数字 每次从未排序的区域选择一个数字，插入到已排序的数字的正确位置
# 例如 [1,2,3,4,6,7,8,5] 此时将5插入4的后面 实现的原理是5和8换 5和7换 直到5和6换完成
# 时间复杂度 由于n循环嵌套while循环 所以时间复杂度是O(n^2) 平方阶
def sort_insert(li):
    for i in range(1, len(li)):
        temp = li[i]
        j = i - 1
        while j >= 0 and temp < li[j]:
            li[j + 1] = li[j]
            j = j - 1
        li[j + 1] = temp
        print(li)


list1 = []
for x in range(10):
    list1.append(random.randint(1, 1001))
print(list1)
sort_insert(list1)
